{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Action2多辆车的路径规划 VRP：     \n",
    "\n",
    "条件：经过中国33个城市，一共4辆车，每辆车最大行驶10000公里     \n",
    "\n",
    "目标：使得每辆车的行驶里程数更接近     \n",
    "\n",
    "需要注意：在VRP问题中，路径上给点赋的index和点实际的index不一样，需要使用IndexToNode方法进行转换才能得到实际的index     \n",
    "\n",
    "1、完成带有约束条件的VRP问题（20points）     2、结果正确（10points）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "from ortools.constraint_solver import routing_enums_pb2,pywrapcp\n",
    "\n",
    "class tsp(object):\n",
    "    def __init__(self, city_names=None):\n",
    "        # 设置城市名称\n",
    "        self.df = pd.read_excel('./cities.xlsx')\n",
    "        self.all_city = self.df['name'].values\n",
    "        if city_names is not None:\n",
    "            self.city_names = city_names\n",
    "            self.df = self.df[self.df['name'].isin(city_names)]\n",
    "        else:\n",
    "            self.city_names = self.all_city\n",
    "            \n",
    "    def create_data_model(self):\n",
    "        data = {}\n",
    "        temp = pd.read_excel('./distance.xlsx', index_col=0)\n",
    "        # 按照city_names进行筛选\n",
    "        temp = temp[(temp.index.isin(self.city_names))][self.city_names]\n",
    "        print(temp)\n",
    "        data['distance_matrix'] = temp.values/1000\n",
    "        \n",
    "        data['num_vehicles'] = 1 # 车的数量\n",
    "        data['depot'] = 0 # 从哪个点出发\n",
    "        return data\n",
    "    \n",
    "    # 输出结果\n",
    "    def get_solution(self,manager, routing, solution):\n",
    "        print('总行驶里程: {} 公里'.format(solution.ObjectiveValue()))\n",
    "        index = routing.Start(0)\n",
    "#         plan_output = '车辆的路径:\\n'\n",
    "        route = []\n",
    "        route_distance = 0\n",
    "        while not routing.IsEnd(index):\n",
    "            # 使用indextonode将manager中的index转换为distance_matrix中的index\n",
    "#             plan_output += ' {} ->'.format(city_names[manager.IndexToNode(index)])\n",
    "            index_show = manager.IndexToNode(index)\n",
    "            # 添加到route\n",
    "            route.append(index_show)\n",
    "            previous_index = index\n",
    "            # 走到下一个节点\n",
    "            index = solution.Value(routing.NextVar(index))\n",
    "            # 统计previous_index到index节点的距离\n",
    "            route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)\n",
    "        return route,route_distance\n",
    "    \n",
    "    def work(self):\n",
    "        # step1，初始化得到三个参数字典\n",
    "        data = self.create_data_model()\n",
    "        # step2，创建路线管理,tsp_size（城市数量）, num_vehicles（车的数量）, depot（原点）\n",
    "        manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),\n",
    "                                               data['num_vehicles'], data['depot'])\n",
    "\n",
    "        # step3，创建 Routing Model.\n",
    "        routing = pywrapcp.RoutingModel(manager)\n",
    "\n",
    "        # step4，计算两点之间的距离。输入的是manager中两个节点的index，输出的是节点之间的距离\n",
    "        def distance_callback(from_index, to_index):\n",
    "            # 将index转换为distance_matrix中的节点index\n",
    "            # Convert from routing variable Index to distance matrix NodeIndex.\n",
    "            from_node = manager.IndexToNode(from_index)\n",
    "            to_node = manager.IndexToNode(to_index)\n",
    "            return data['distance_matrix'][from_node][to_node]\n",
    "        # 注册函数\n",
    "        transit_callback_index = routing.RegisterTransitCallback(distance_callback)\n",
    "\n",
    "        # Define cost of each arc.\n",
    "        routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)\n",
    "        #step5，设置参数策略\n",
    "        # Setting first solution heuristic.\n",
    "        search_parameters = pywrapcp.DefaultRoutingSearchParameters()\n",
    "        search_parameters.first_solution_strategy = (\n",
    "            routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)\n",
    "\n",
    "        # step6，求解路径规划\n",
    "        solution = routing.SolveWithParameters(search_parameters)\n",
    "        # step7，输出结果\n",
    "        route, route_distance = self.get_solution(manager,routing,solution)\n",
    "        return route,route_distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 测试1：使用全量的城市，不对city_names进行筛选"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "总行驶里程: 19799 公里\n",
      "[0, 6, 22, 21, 23, 24, 26, 27, 25, 12, 32, 11, 31, 30, 10, 9, 8, 15, 13, 28, 29, 14, 20, 17, 18, 19, 7, 5, 16, 1, 4, 2, 3]\n",
      "19799\n"
     ]
    }
   ],
   "source": [
    "model = tsp()\n",
    "route, route_distance = model.work()\n",
    "print(route)\n",
    "print(route_distance)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 测试2：city_names = ['北京', '天津', '南京']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "         北京      天津       南京\n",
      "北京        0  122476  1002497\n",
      "天津   122476       0   935319\n",
      "南京  1002497  935319        0\n",
      "         北京      天津       南京\n",
      "北京        0  122476  1002497\n",
      "天津   122476       0   935319\n",
      "南京  1002497  935319        0\n",
      "总行驶里程: 2059 公里\n",
      "[0, 1, 2]\n",
      "2059\n"
     ]
    }
   ],
   "source": [
    "city_names = ['北京', '天津', '南京']\n",
    "model = tsp(city_names = city_names)\n",
    "model.create_data_model()\n",
    "route, route_distance = model.work()\n",
    "print(route)\n",
    "print(route_distance)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.0 64-bit ('Bi_env': venv)",
   "language": "python",
   "name": "python38064bitbienvvenvba07af95a1bb4b078aa8134bba84dff2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
